#include<iostream>
using namespace std;
#include<vector>
#include<string>
class Solution {
public:
    vector<string> ans;
    string path;
    void dfs(int n) {
        if (n == 0) {
            ans.push_back(path);
            return;
        }
        path.push_back('1');
        dfs(n - 1);
        path.pop_back();
        if (path.size() == 0 || (path.size() && path.back() == '1')) {
            path.push_back('0');
            dfs(n - 1);
            path.pop_back();
        }
    }
    vector<string> validStrings(int n) {
        dfs(n);
        return ans;
    }
};
int main() {
    Solution().validStrings(3);
}